using System;
using System.Collections.Generic;
using System.Text;
using VisualizationPackage.FileLoader;
using System.Collections.ObjectModel;
using System.Drawing;

namespace VisualizationPackage.IsoSurfaces
{
    public class MarchingCubes
    {
        private int _Variable;
        public int Variable
        {
            get { return _Variable; }
            set { _Variable = value; }
        }
        private ColorMap _map;
        public ColorMap colorsMap
        {
            get { return _map; }
            set { _map = value; }
        }

        public MarchingCubes(ColorMap mp, int distVar)
        {
            _map = mp;
            Variable = distVar;
        }

        public ReadOnlyCollection<Polygon> IsoSurfaces(Visualization.Zone data)
        {
            List<Polygon> Polys = new List<Polygon>();
            foreach (ColorMapNode iso in colorsMap.Map)
                Polys.AddRange(IsoSurfaces(data, iso.Value, iso.NodeColor));
            return new ReadOnlyCollection<Polygon>(Polys);
        }

        public List<Polygon> IsoSurfaces(Visualization.Zone data, double dist, Color clr)
        {
            if (data.ElementType == Visualization.ElementType.Tetrahedron)
                return MarchinTetrahederons(data, dist, clr);
            if (data.ElementType != Visualization.ElementType.FEBrick &&
                data.ElementType != Visualization.ElementType.IJKBrick)
                return new List<Polygon>();
            List<Polygon> polys = new List<Polygon>();
            foreach (Visualization.Element voxel in data.Elements)
            {
                int index = 0;
                for (int i = 0; i < 4; i++)
                {
                    double Currentdist = data.Vertices[data.Faces[voxel.GetBrickBottomFace()].Vertices[i]].Data[Variable];
                    if (Currentdist < dist)
                        index |= 1 << i;
                }
                for (int i = 0; i < 4; i++)
                {
                    double Currentdist = data.Vertices[data.Faces[voxel.GetBrickTopFace()].Vertices[i]].Data[Variable];
                    if (Currentdist < dist)
                        index |= 1 << (i + 4);
                }
                Polygon p = new Polygon();
                p.DrawingColor = clr;
                for (int i = 0; i < 13; i++)
                {
                    if (aCases[index, i] == -1)
                        break;
                    Visualization.Vertex v1, v2;
                    int VertexIndex1 = EdgesMap[aCases[index, i], 0]
                        , VertexIndex2 = EdgesMap[aCases[index, i], 1];
                    if (VertexIndex1 < 4)
                        v1 = data.Vertices[data.Faces[voxel.GetBrickBottomFace()].Vertices[VertexIndex1]];
                    else
                        v1 = data.Vertices[data.Faces[voxel.GetBrickTopFace()].Vertices[VertexIndex1 - 4]];
                    if (VertexIndex2 < 4)
                        v2 = data.Vertices[data.Faces[voxel.GetBrickBottomFace()].Vertices[VertexIndex2]];
                    else
                        v2 = data.Vertices[data.Faces[voxel.GetBrickTopFace()].Vertices[VertexIndex2 - 4]];

                    p.Add(Interpolate(v1, v2, dist));
                    if (p.Vertics.Count == 3)
                    {
                        polys.Add(p);
                        p = new Polygon();
                        p.DrawingColor = clr;
                    }
                }
            }
            return polys;
        }

        private List<Polygon> MarchinTetrahederons(Visualization.Zone data, double dist, Color clr)
        {
            List<Polygon> polys = new List<Polygon>();
            foreach (Visualization.Element tetra in data.Elements)
            {
                int index = 0;
                double DistPoint0 = data.Vertices[data.Faces[tetra.Faces[3]].Vertices[0]].Data[Variable];
                double DistPoint1 = data.Vertices[data.Faces[tetra.Faces[3]].Vertices[1]].Data[Variable];
                double DistPoint2 = data.Vertices[data.Faces[tetra.Faces[3]].Vertices[2]].Data[Variable];
                // to be revised
                double DistPoint3 = data.Vertices[data.Faces[tetra.Faces[0]].Vertices[2]].Data[Variable];
                if (DistPoint0 < dist) index |= 1;
                if (DistPoint1 < dist) index |= 2;
                if (DistPoint2 < dist) index |= 4;
                if (DistPoint3 < dist) index |= 8;
                if (index > 7) index = (~index) & 0x7;
                Polygon p = new Polygon();
                p.DrawingColor = clr;
                for (int i = 0; i < 6; i++)
                {
                    if (tCases[index, i] == -1) break;
                    Visualization.Vertex v1, v2;
                    int VertexIndex1 = TetrahederonEdges[tCases[index, i], 0]
                        , VertexIndex2 = TetrahederonEdges[tCases[index, i], 1];
                    if (VertexIndex1 < 3)
                        v1 = data.Vertices[data.Faces[tetra.Faces[3]].Vertices[VertexIndex1]];
                    else // to be revised
                        v1 = data.Vertices[data.Faces[tetra.Faces[0]].Vertices[2]];
                    if (VertexIndex2 < 3)
                        v2 = data.Vertices[data.Faces[tetra.Faces[3]].Vertices[VertexIndex2]];
                    else // to be revised
                        v2 = data.Vertices[data.Faces[tetra.Faces[0]].Vertices[2]];

                    p.Add(Interpolate(v1, v2, dist));
                    if (p.Vertics.Count == 3)
                    {
                        polys.Add(p);
                        p = new Polygon();
                        p.DrawingColor = clr;
                    }
                }
            }
            return polys;
        }

        private Vertex Interpolate(Visualization.Vertex v1, Visualization.Vertex v2, double dist)
        {
            if (v1.Data[Variable] > v2.Data[Variable])
                return Interpolate(v2, v1, dist);
            if (v1.Data[Variable] == v2.Data[Variable])
                return new Vertex(v1);
            Vertex v = new Vertex();
            double P = (dist - v1.Data[Variable]) / (v2.Data[Variable] - v1.Data[Variable]);
            v.X = v1.Position.x + P * (v2.Position.x - v1.Position.x);
            v.Y = v1.Position.y + P * (v2.Position.y - v1.Position.y);
            v.Z = v1.Position.z + P * (v2.Position.z - v1.Position.z);
            //			if (!isBetween(v1.Position.x, v2.Position.x, v["X"]) || 
            ///				!isBetween(v1.Position.y, v2.Position.y, v["Y"]) || 
            //				!isBetween(v1.Position.z, v2.Position.z, v["Z"]))
            //				throw new Exception("wrong interpolation");
            return v;
        }

        private bool isBetween(double Lower, double Upper, double within)
        {
            if (Upper < Lower)
                return isBetween(Upper, Lower, within);
            return (Lower <= within) && (Upper >= within);
        }

        public static short[,] EdgesMap = new short[,]{
			{0,1}, {1,2}, {2,3}, {3,0}, {4,5}, {5,6},
			{6,7}, {7,4}, {0,4}, {1,5}, {2,6}, {3,7}
		};

        public static short[,] TetrahederonEdges = new short[,] {
			{0,1}, {1,2}, {2,0}, {0,3}, {1,3}, {2,3}		
		};

        public static short[,] aCases = new short[,]
		{
			{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 3, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 0, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 3, 1, 8, 1, 9,-1,-1,-1,-1,-1,-1,-1},
			{10, 1, 2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 3, 0, 1, 2,10,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 0, 2, 9, 2,10,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 2, 8, 2,10, 8, 8,10, 9,-1,-1,-1,-1},
			{11, 2, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{11, 2, 0,11, 0, 8,-1,-1,-1,-1,-1,-1,-1},
			{11, 2, 3, 0, 1, 9,-1,-1,-1,-1,-1,-1,-1},
			{ 2, 1,11, 1, 9,11,11, 9, 8,-1,-1,-1,-1},
			{10, 1, 3,10, 3,11,-1,-1,-1,-1,-1,-1,-1},
			{ 1, 0,10, 0, 8,10,10, 8,11,-1,-1,-1,-1},
			{ 0, 3, 9, 3,11, 9, 9,11,10,-1,-1,-1,-1},
			{ 8,10, 9, 8,11,10,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 4, 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 0, 4, 3, 4, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 1, 9, 0, 8, 4, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 4, 1, 4, 7, 1, 1, 7, 3,-1,-1,-1,-1},
			{10, 1, 2, 8, 4, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 2,10, 1, 0, 4, 7, 0, 7, 3,-1,-1,-1,-1},
			{ 4, 7, 8, 0, 2,10, 0,10, 9,-1,-1,-1,-1},
			{ 2, 7, 3, 2, 9, 7, 7, 9, 4, 2,10, 9,-1},
			{ 2, 3,11, 7, 8, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 7,11, 4,11, 2, 4, 4, 2, 0,-1,-1,-1,-1},
			{ 3,11, 2, 4, 7, 8, 9, 0, 1,-1,-1,-1,-1},
			{ 2, 7,11, 2, 1, 7, 1, 4, 7, 1, 9, 4,-1},
			{ 8, 4, 7,11,10, 1,11, 1, 3,-1,-1,-1,-1},
			{11, 4, 7, 1, 4,11, 1,11,10, 1, 0, 4,-1},
			{ 3, 8, 0, 7,11, 4,11, 9, 4,11,10, 9,-1},
			{ 7,11, 4, 4,11, 9,11,10, 9,-1,-1,-1,-1},
			{ 9, 5, 4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 0, 8, 4, 9, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 5, 4, 0, 5, 0, 1,-1,-1,-1,-1,-1,-1,-1},
			{ 4, 8, 5, 8, 3, 5, 5, 3, 1,-1,-1,-1,-1},
			{ 2,10, 1, 9, 5, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 8, 3, 5, 4, 9,10, 1, 2,-1,-1,-1,-1},
			{10, 5, 2, 5, 4, 2, 2, 4, 0,-1,-1,-1,-1},
			{ 3, 4, 8, 3, 2, 4, 2, 5, 4, 2,10, 5,-1},
			{11, 2, 3, 9, 5, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 5, 4, 8,11, 2, 8, 2, 0,-1,-1,-1,-1},
			{ 3,11, 2, 1, 5, 4, 1, 4, 0,-1,-1,-1,-1},
			{ 8, 5, 4, 2, 5, 8, 2, 8,11, 2, 1, 5,-1},
			{ 5, 4, 9, 1, 3,11, 1,11,10,-1,-1,-1,-1},
			{ 0, 9, 1, 4, 8, 5, 8,10, 5, 8,11,10,-1},
			{ 3, 4, 0, 3,10, 4, 4,10, 5, 3,11,10,-1},
			{ 4, 8, 5, 5, 8,10, 8,11,10,-1,-1,-1,-1},
			{ 9, 5, 7, 9, 7, 8,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 9, 3, 9, 5, 3, 3, 5, 7,-1,-1,-1,-1},
			{ 8, 0, 7, 0, 1, 7, 7, 1, 5,-1,-1,-1,-1},
			{ 1, 7, 3, 1, 5, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 1, 2,10, 5, 7, 8, 5, 8, 9,-1,-1,-1,-1},
			{ 9, 1, 0,10, 5, 2, 5, 3, 2, 5, 7, 3,-1},
			{ 5, 2,10, 8, 2, 5, 8, 5, 7, 8, 0, 2,-1},
			{10, 5, 2, 2, 5, 3, 5, 7, 3,-1,-1,-1,-1},
			{11, 2, 3, 8, 9, 5, 8, 5, 7,-1,-1,-1,-1},
			{ 9, 2, 0, 9, 7, 2, 2, 7,11, 9, 5, 7,-1},
			{ 0, 3, 8, 2, 1,11, 1, 7,11, 1, 5, 7,-1},
			{ 2, 1,11,11, 1, 7, 1, 5, 7,-1,-1,-1,-1},
			{ 3, 9, 1, 3, 8, 9, 7,11,10, 7,10, 5,-1},
			{ 9, 1, 0,10, 7,11,10, 5, 7,-1,-1,-1,-1},
			{ 3, 8, 0, 7,10, 5, 7,11,10,-1,-1,-1,-1},
			{11, 5, 7,11,10, 5,-1,-1,-1,-1,-1,-1,-1},
			{10, 6, 5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 3, 0,10, 6, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 1, 9, 5,10, 6,-1,-1,-1,-1,-1,-1,-1},
			{10, 6, 5, 9, 8, 3, 9, 3, 1,-1,-1,-1,-1},
			{ 1, 2, 6, 1, 6, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 8, 3, 2, 6, 5, 2, 5, 1,-1,-1,-1,-1},
			{ 5, 9, 6, 9, 0, 6, 6, 0, 2,-1,-1,-1,-1},
			{ 9, 6, 5, 3, 6, 9, 3, 9, 8, 3, 2, 6,-1},
			{ 3,11, 2,10, 6, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 6, 5,10, 2, 0, 8, 2, 8,11,-1,-1,-1,-1},
			{ 1, 9, 0, 6, 5,10,11, 2, 3,-1,-1,-1,-1},
			{ 1,10, 2, 5, 9, 6, 9,11, 6, 9, 8,11,-1},
			{11, 6, 3, 6, 5, 3, 3, 5, 1,-1,-1,-1,-1},
			{ 0, 5, 1, 0,11, 5, 5,11, 6, 0, 8,11,-1},
			{ 0, 5, 9, 0, 3, 5, 3, 6, 5, 3,11, 6,-1},
			{ 5, 9, 6, 6, 9,11, 9, 8,11,-1,-1,-1,-1},
			{10, 6, 5, 4, 7, 8,-1,-1,-1,-1,-1,-1,-1},
			{ 5,10, 6, 7, 3, 0, 7, 0, 4,-1,-1,-1,-1},
			{ 5,10, 6, 0, 1, 9, 8, 4, 7,-1,-1,-1,-1},
			{ 4, 5, 9, 6, 7,10, 7, 1,10, 7, 3, 1,-1},
			{ 7, 8, 4, 5, 1, 2, 5, 2, 6,-1,-1,-1,-1},
			{ 4, 1, 0, 4, 5, 1, 6, 7, 3, 6, 3, 2,-1},
			{ 9, 4, 5, 8, 0, 7, 0, 6, 7, 0, 2, 6,-1},
			{ 4, 5, 9, 6, 3, 2, 6, 7, 3,-1,-1,-1,-1},
			{ 7, 8, 4, 2, 3,11,10, 6, 5,-1,-1,-1,-1},
			{11, 6, 7,10, 2, 5, 2, 4, 5, 2, 0, 4,-1},
			{11, 6, 7, 8, 0, 3, 1,10, 2, 9, 4, 5,-1},
			{ 6, 7,11, 1,10, 2, 9, 4, 5,-1,-1,-1,-1},
			{ 6, 7,11, 4, 5, 8, 5, 3, 8, 5, 1, 3,-1},
			{ 6, 7,11, 4, 1, 0, 4, 5, 1,-1,-1,-1,-1},
			{ 4, 5, 9, 3, 8, 0,11, 6, 7,-1,-1,-1,-1},
			{ 9, 4, 5, 7,11, 6,-1,-1,-1,-1,-1,-1,-1},
			{10, 6, 4,10, 4, 9,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 3, 0, 9,10, 6, 9, 6, 4,-1,-1,-1,-1},
			{ 1,10, 0,10, 6, 0, 0, 6, 4,-1,-1,-1,-1},
			{ 8, 6, 4, 8, 1, 6, 6, 1,10, 8, 3, 1,-1},
			{ 9, 1, 4, 1, 2, 4, 4, 2, 6,-1,-1,-1,-1},
			{ 1, 0, 9, 3, 2, 8, 2, 4, 8, 2, 6, 4,-1},
			{ 2, 4, 0, 2, 6, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 2, 8, 8, 2, 4, 2, 6, 4,-1,-1,-1,-1},
			{ 2, 3,11, 6, 4, 9, 6, 9,10,-1,-1,-1,-1},
			{ 0,10, 2, 0, 9,10, 4, 8,11, 4,11, 6,-1},
			{10, 2, 1,11, 6, 3, 6, 0, 3, 6, 4, 0,-1},
			{10, 2, 1,11, 4, 8,11, 6, 4,-1,-1,-1,-1},
			{ 1, 4, 9,11, 4, 1,11, 1, 3,11, 6, 4,-1},
			{ 0, 9, 1, 4,11, 6, 4, 8,11,-1,-1,-1,-1},
			{11, 6, 3, 3, 6, 0, 6, 4, 0,-1,-1,-1,-1},
			{ 8, 6, 4, 8,11, 6,-1,-1,-1,-1,-1,-1,-1},
			{ 6, 7,10, 7, 8,10,10, 8, 9,-1,-1,-1,-1},
			{ 9, 3, 0, 6, 3, 9, 6, 9,10, 6, 7, 3,-1},
			{ 6, 1,10, 6, 7, 1, 7, 0, 1, 7, 8, 0,-1},
			{ 6, 7,10,10, 7, 1, 7, 3, 1,-1,-1,-1,-1},
			{ 7, 2, 6, 7, 9, 2, 2, 9, 1, 7, 8, 9,-1},
			{ 1, 0, 9, 3, 6, 7, 3, 2, 6,-1,-1,-1,-1},
			{ 8, 0, 7, 7, 0, 6, 0, 2, 6,-1,-1,-1,-1},
			{ 2, 7, 3, 2, 6, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 7,11, 6, 3, 8, 2, 8,10, 2, 8, 9,10,-1},
			{11, 6, 7,10, 0, 9,10, 2, 0,-1,-1,-1,-1},
			{ 2, 1,10, 7,11, 6, 8, 0, 3,-1,-1,-1,-1},
			{ 1,10, 2, 6, 7,11,-1,-1,-1,-1,-1,-1,-1},
			{ 7,11, 6, 3, 9, 1, 3, 8, 9,-1,-1,-1,-1},
			{ 9, 1, 0,11, 6, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 3, 8,11, 6, 7,-1,-1,-1,-1,-1,-1,-1},
			{11, 6, 7,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{11, 7, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 8, 3,11, 7, 6,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 0, 1,11, 7, 6,-1,-1,-1,-1,-1,-1,-1},
			{ 7, 6,11, 3, 1, 9, 3, 9, 8,-1,-1,-1,-1},
			{ 1, 2,10, 6,11, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 2,10, 1, 7, 6,11, 8, 3, 0,-1,-1,-1,-1},
			{11, 7, 6,10, 9, 0,10, 0, 2,-1,-1,-1,-1},
			{ 7, 6,11, 3, 2, 8, 8, 2,10, 8,10, 9,-1},
			{ 2, 3, 7, 2, 7, 6,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 7, 0, 7, 6, 0, 0, 6, 2,-1,-1,-1,-1},
			{ 1, 9, 0, 3, 7, 6, 3, 6, 2,-1,-1,-1,-1},
			{ 7, 6, 2, 7, 2, 9, 2, 1, 9, 7, 9, 8,-1},
			{ 6,10, 7,10, 1, 7, 7, 1, 3,-1,-1,-1,-1},
			{ 6,10, 1, 6, 1, 7, 7, 1, 0, 7, 0, 8,-1},
			{ 9, 0, 3, 6, 9, 3, 6,10, 9, 6, 3, 7,-1},
			{ 6,10, 7, 7,10, 8,10, 9, 8,-1,-1,-1,-1},
			{ 8, 4, 6, 8, 6,11,-1,-1,-1,-1,-1,-1,-1},
			{11, 3, 6, 3, 0, 6, 6, 0, 4,-1,-1,-1,-1},
			{ 0, 1, 9, 4, 6,11, 4,11, 8,-1,-1,-1,-1},
			{ 1, 9, 4,11, 1, 4,11, 3, 1,11, 4, 6,-1},
			{10, 1, 2,11, 8, 4,11, 4, 6,-1,-1,-1,-1},
			{10, 1, 2,11, 3, 6, 6, 3, 0, 6, 0, 4,-1},
			{ 0, 2,10, 0,10, 9, 4,11, 8, 4, 6,11,-1},
			{ 2,11, 3, 6, 9, 4, 6,10, 9,-1,-1,-1,-1},
			{ 3, 8, 2, 8, 4, 2, 2, 4, 6,-1,-1,-1,-1},
			{ 2, 0, 4, 2, 4, 6,-1,-1,-1,-1,-1,-1,-1},
			{ 1, 9, 0, 3, 8, 2, 2, 8, 4, 2, 4, 6,-1},
			{ 9, 4, 1, 1, 4, 2, 4, 6, 2,-1,-1,-1,-1},
			{ 8, 4, 6, 8, 6, 1, 6,10, 1, 8, 1, 3,-1},
			{ 1, 0,10,10, 0, 6, 0, 4, 6,-1,-1,-1,-1},
			{ 8, 0, 3, 9, 6,10, 9, 4, 6,-1,-1,-1,-1},
			{10, 4, 6,10, 9, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 5, 4, 7, 6,11,-1,-1,-1,-1,-1,-1,-1},
			{ 4, 9, 5, 3, 0, 8,11, 7, 6,-1,-1,-1,-1},
			{ 6,11, 7, 4, 0, 1, 4, 1, 5,-1,-1,-1,-1},
			{ 6,11, 7, 4, 8, 5, 5, 8, 3, 5, 3, 1,-1},
			{ 6,11, 7, 1, 2,10, 9, 5, 4,-1,-1,-1,-1},
			{11, 7, 6, 8, 3, 0, 1, 2,10, 9, 5, 4,-1},
			{11, 7, 6,10, 5, 2, 2, 5, 4, 2, 4, 0,-1},
			{ 7, 4, 8, 2,11, 3,10, 5, 6,-1,-1,-1,-1},
			{ 4, 9, 5, 6, 2, 3, 6, 3, 7,-1,-1,-1,-1},
			{ 9, 5, 4, 8, 7, 0, 0, 7, 6, 0, 6, 2,-1},
			{ 4, 0, 1, 4, 1, 5, 6, 3, 7, 6, 2, 3,-1},
			{ 7, 4, 8, 5, 2, 1, 5, 6, 2,-1,-1,-1,-1},
			{ 4, 9, 5, 6,10, 7, 7,10, 1, 7, 1, 3,-1},
			{ 5, 6,10, 0, 9, 1, 8, 7, 4,-1,-1,-1,-1},
			{ 5, 6,10, 7, 0, 3, 7, 4, 0,-1,-1,-1,-1},
			{10, 5, 6, 4, 8, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 5, 6, 9, 6,11, 9, 9,11, 8,-1,-1,-1,-1},
			{ 0, 9, 5, 0, 5, 3, 3, 5, 6, 3, 6,11,-1},
			{ 0, 1, 5, 0, 5,11, 5, 6,11, 0,11, 8,-1},
			{11, 3, 6, 6, 3, 5, 3, 1, 5,-1,-1,-1,-1},
			{ 1, 2,10, 5, 6, 9, 9, 6,11, 9,11, 8,-1},
			{ 1, 0, 9, 6,10, 5,11, 3, 2,-1,-1,-1,-1},
			{ 6,10, 5, 2, 8, 0, 2,11, 8,-1,-1,-1,-1},
			{ 3, 2,11,10, 5, 6,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 5, 6, 3, 9, 6, 3, 8, 9, 3, 6, 2,-1},
			{ 5, 6, 9, 9, 6, 0, 6, 2, 0,-1,-1,-1,-1},
			{ 0, 3, 8, 2, 5, 6, 2, 1, 5,-1,-1,-1,-1},
			{ 1, 6, 2, 1, 5, 6,-1,-1,-1,-1,-1,-1,-1},
			{10, 5, 6, 9, 3, 8, 9, 1, 3,-1,-1,-1,-1},
			{ 0, 9, 1, 5, 6,10,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 0, 3,10, 5, 6,-1,-1,-1,-1,-1,-1,-1},
			{10, 5, 6,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{11, 7, 5,11, 5,10,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 0, 8, 7, 5,10, 7,10,11,-1,-1,-1,-1},
			{ 9, 0, 1,10,11, 7,10, 7, 5,-1,-1,-1,-1},
			{ 3, 1, 9, 3, 9, 8, 7,10,11, 7, 5,10,-1},
			{ 2,11, 1,11, 7, 1, 1, 7, 5,-1,-1,-1,-1},
			{ 0, 8, 3, 2,11, 1, 1,11, 7, 1, 7, 5,-1},
			{ 9, 0, 2, 9, 2, 7, 2,11, 7, 9, 7, 5,-1},
			{11, 3, 2, 8, 5, 9, 8, 7, 5,-1,-1,-1,-1},
			{10, 2, 5, 2, 3, 5, 5, 3, 7,-1,-1,-1,-1},
			{ 5,10, 2, 8, 5, 2, 8, 7, 5, 8, 2, 0,-1},
			{ 9, 0, 1,10, 2, 5, 5, 2, 3, 5, 3, 7,-1},
			{ 1,10, 2, 5, 8, 7, 5, 9, 8,-1,-1,-1,-1},
			{ 1, 3, 7, 1, 7, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 7, 0, 0, 7, 1, 7, 5, 1,-1,-1,-1,-1},
			{ 0, 3, 9, 9, 3, 5, 3, 7, 5,-1,-1,-1,-1},
			{ 9, 7, 5, 9, 8, 7,-1,-1,-1,-1,-1,-1,-1},
			{ 4, 5, 8, 5,10, 8, 8,10,11,-1,-1,-1,-1},
			{ 3, 0, 4, 3, 4,10, 4, 5,10, 3,10,11,-1},
			{ 0, 1, 9, 4, 5, 8, 8, 5,10, 8,10,11,-1},
			{ 5, 9, 4, 1,11, 3, 1,10,11,-1,-1,-1,-1},
			{ 8, 4, 5, 2, 8, 5, 2,11, 8, 2, 5, 1,-1},
			{ 3, 2,11, 1, 4, 5, 1, 0, 4,-1,-1,-1,-1},
			{ 9, 4, 5, 8, 2,11, 8, 0, 2,-1,-1,-1,-1},
			{11, 3, 2, 9, 4, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 8, 4, 3, 4, 2, 2, 4, 5, 2, 5,10,-1},
			{10, 2, 5, 5, 2, 4, 2, 0, 4,-1,-1,-1,-1},
			{ 0, 3, 8, 5, 9, 4,10, 2, 1,-1,-1,-1,-1},
			{ 2, 1,10, 9, 4, 5,-1,-1,-1,-1,-1,-1,-1},
			{ 4, 5, 8, 8, 5, 3, 5, 1, 3,-1,-1,-1,-1},
			{ 5, 0, 4, 5, 1, 0,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 8, 0, 4, 5, 9,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 4, 5,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 7, 4,11, 4, 9,11,11, 9,10,-1,-1,-1,-1},
			{ 3, 0, 8, 7, 4,11,11, 4, 9,11, 9,10,-1},
			{11, 7, 4, 1,11, 4, 1,10,11, 1, 4, 0,-1},
			{ 8, 7, 4,11, 1,10,11, 3, 1,-1,-1,-1,-1},
			{ 2,11, 7, 2, 7, 1, 1, 7, 4, 1, 4, 9,-1},
			{ 3, 2,11, 4, 8, 7, 9, 1, 0,-1,-1,-1,-1},
			{ 7, 4,11,11, 4, 2, 4, 0, 2,-1,-1,-1,-1},
			{ 2,11, 3, 7, 4, 8,-1,-1,-1,-1,-1,-1,-1},
			{ 2, 3, 7, 2, 7, 9, 7, 4, 9, 2, 9,10,-1},
			{ 4, 8, 7, 0,10, 2, 0, 9,10,-1,-1,-1,-1},
			{ 2, 1,10, 0, 7, 4, 0, 3, 7,-1,-1,-1,-1},
			{10, 2, 1, 8, 7, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 1, 4, 4, 1, 7, 1, 3, 7,-1,-1,-1,-1},
			{ 1, 0, 9, 8, 7, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 4, 0, 3, 7, 4,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 7, 4,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 9,10, 8,10,11,-1,-1,-1,-1,-1,-1,-1},
			{ 0, 9, 3, 3, 9,11, 9,10,11,-1,-1,-1,-1},
			{ 1,10, 0, 0,10, 8,10,11, 8,-1,-1,-1,-1},
			{10, 3, 1,10,11, 3,-1,-1,-1,-1,-1,-1,-1},
			{ 2,11, 1, 1,11, 9,11, 8, 9,-1,-1,-1,-1},
			{11, 3, 2, 0, 9, 1,-1,-1,-1,-1,-1,-1,-1},
			{11, 0, 2,11, 8, 0,-1,-1,-1,-1,-1,-1,-1},
			{11, 3, 2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 3, 8, 2, 2, 8,10, 8, 9,10,-1,-1,-1,-1},
			{ 9, 2, 0, 9,10, 2,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 0, 3, 1,10, 2,-1,-1,-1,-1,-1,-1,-1},
			{10, 2, 1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 1, 3, 8, 9, 1,-1,-1,-1,-1,-1,-1,-1},
			{ 9, 1, 0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{ 8, 0, 3,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},
			{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
		};

        public static short[,] tCases = new short[,] {
			{-1, -1, -1, -1, -1, -1, -1},
			{ 0,  2,  3, -1, -1, -1, -1},
			{ 0,  1,  4, -1, -1, -1, -1},
			{ 2,  1,  4,  2,  3,  4, -1},
			{ 1,  2,  5, -1, -1, -1, -1},
			{ 0,  3,  5,  0,  1,  5, -1},
			{ 0,  2,  5,  0,  4,  5, -1},
			{ 3,  4,  5, -1, -1, -1, -1}
		};
    }
}
